KONTEXTOVÁ GRAMATIKA
Vymezení a popis přirozených jazyků (zejména jejich syntaktické struktury); typ ↗generativní gramatiky v ↗Chomského hierarchii gramatik a jazyků; nazývá se také gramatikou typu 1. Přepisovací pravidla k.g. mají tuto podobu: αXβ → αγβ, kde X je neterminální symbol, α a β jsou řetězce složené z terminálů a/nebo neterminálů, γ je neprázdný řetězec, na který se v kontextu (α, β) přepisuje symbol X; k.g. je tedy typem gramatiky nezkracující, tj. délka větných forem vzniklých v průběhu derivace neklesá. Alternativní definicí je toto omezení kladené na pravidla: α → β, kde α a β jsou řetězce, kde α obsahuje aspoň jeden neterminál a řetězec β není kratší než řetězec α. Protějškem k.g. mezi automaty je tzv. lineárně omezený automat jakožto speciální případ Turingova stroje. K.g. generují třídu ↗kontextových jazyků (což je podtřída rekurzivních množin), dokážou tedy generovat i všechny ↗bezkontextové jazyky a navíc dokážou modelovat i nebezkontextové, tj. nezapouštějící struktury typu a1, a2, …, an, b1, b2, …, bn (n ≥ 0), kde prvky ai a bi jsou spolu v syntaktickém vztahu, a struktury s nespojitými/nesouvislými složkami, v nichž se mezi členy složky nachází – z hlediska slovosledu – element, který do ní nepatří. Tyto schopnosti k.g. jsou dány tím, že na rozdíl od ↗bezkontextových gramatik dokážou k.g. přehazovat symboly v průběhu derivace. K.g. představují horní mez strukturní složitosti přirozených jazyků; struktura všech přirozených jazyků světa se dá postihnout jistou podtřídou k.g. Reálně se při modelování přirozených jazyků pracuje s gramatikami, které jsou konzervativním rozšířením bezkontextových gramatik (např. gramatiky typu tree‑adjoining, v nichž se operuje nikoli s řetězci, nýbrž se stromovými strukturami).
- Češka, M. Gramatiky a jazyky, 1992.
- Harrison, M. A. Introduction to Formal Language Theory, 1978.
- Hausser, R. Foundations of Computational Linguistics. Human-Computer Communication in Natural Language, 2001.
- Hopcroft, J. E. & J. D. Ullman. Formal Languages and their Relation to Automata, 1978.
- Chomsky, N. Syntactic Structures, 1957 (č. překlad: Syntaktické struktury, 1966).
- Chomsky, N. On Certain Formal Properties of Grammars. Information and Control 2, 1959, 137–167.
- Chytil, M. Teorie automatů a formálních jazyků, 1978.
- Chytil, M. Automaty a gramatiky, 1984.
- Krulee, G. K. Computer Processing of Natural Language, 1991.
- Levelt, W. J. M. An Introduction to the Theory of Formal Languages and Automata, 2008.
- Manaster-Ramer, A. (ed.) Mathematics of Language, 1987.
- Martinek, P. Základy teoretické informatiky, 2006.
- Partee, B. H. & A. ter Meulen ad. Mathematical Methods in Linguistics, 1990.
- Rozenberg, G. & A. Salomaa. (eds.) Handbook of Formal Languages 1–3, 1997.
- Salomaa, A. Formal Languages, 1973.
- Savitch, W. J. & E. Bach ad. (eds.) The Formal Complexity of Natural Language, 1987, 320–334.
URL: https://www.czechency.org/slovnik/KONTEXTOVÁ GRAMATIKA (poslední přístup: 21. 11. 2024)
CzechEncy – Nový encyklopedický slovník češtiny
Všechna práva vyhrazena © Masarykova univerzita, Brno 2012–2020
Provozuje Centrum zpracování přirozeného jazyka